package 暑假实习面试.腾讯面试题;

import java.util.Arrays;

public class No5 {

    //No322零钱兑换---最少硬币数量

    public int coinChange(int[] coins, int amount) {

        //从一块钱开始换起
        int[] dp=new int[amount+1];
        //base
        dp[0]=0;

        Arrays.sort(coins);

        for (int i = 1; i <= amount; i++) {
            dp[i]=amount+1;//不用MAX
            for (int coin : coins) {
                if(i-coin<0){//请对钱币进行排序后,才可以使用break
                    break;
                }
                dp[i]=Math.min(dp[i],dp[i-coin]+1);
            }
        }

        return dp[amount]==amount+1?-1:dp[amount];
    }

    public static void main(String[] args) {

    }

}
